Grotołazi

Limit pamięci: 32 MB

Drużyna grotołazów organizuje trening w największej jaskini Bajtogór. Trening polega na przebyciu drogi od komory leżącej najwyżej, do komory leżącej najniżej. Grotołazi mogą posuwać się tylko w dół, tzn. kolejne odwiedzane komory muszą leżeć coraz niżej. Dodatkowo każdy z nich ma wyjść z najwyższej komory innym korytarzem oraz każdy z nich ma wejść do najniższej komory innym korytarzem. Pozostałe korytarze grotołazi mogą pokonywać wspólnie. Ilu grotołazów może odbyć trening jednocześnie?

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia opis jaskini,
• oblicza największą liczbę grotołazów, którzy mogą odbyć trening jednocześnie,
• wypisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita (), równa liczbie komór w jaskini. Komory są ponumerowane liczbami do do w taki sposób, że komora z większym numerem leży niżej od komory z numerem mniejszym. (Najwyższa komora ma numer , a najniższa .) W wierszach o numerach są opisane korytarze wychodzące z kolejnych komór , do komór o wyższych numerach (w wierszu o numerze znajduje się opis korytarzy wychodzących z komory o numerze ). Każdy z tych wierszy zawiera ciąg nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu, , , jest liczbą korytarzy prowadzących z komory do komór o wyższych numerach, natomiast kolejne liczb to numery komór, do których te korytarze prowadzą.

Wyjście

W jedynym wierszu standardowego wyjścia Twój program powinien zapisać jedną liczbę całkowitą, równą maksymalnej liczbie grotołazów mogących wziąć jednocześnie udział w treningu.

Przykład

Dla danych wejściowych:

12
4 3 4 2 5
1 8
2 9 7
2 6 11
1 8
2 9 10
2 10 11
1 12
2 10 12
1 12
1 12

opisujących następującą jaskinię:

poprawną odpowiedzią jest:

3

Autor zadania: Marcin Kubica.